The present invention relates to a residue computing device on a Galois Field, which is most suitable for a residue arithmetic operation and a power-residue arithmetic operation used in elliptic curve cryptography, etc.
While arithmetic operations defined in elliptic curves on an affine space can provide efficient calculations with a microcomputer or the like when the arithmetic operations form a group, particularly, a finite field (Galois Field) is taken by reside arithmetic operations, their calculations result in enormous amounts. Therefore, applications to cryptographs had been considered in the 1980s. It has been found that this type of elliptic curve cryptosystem is capable of implementing security of the same degree with a key having a shorter bit length as compared with the conventional DSA system or RSA system. Attention has thus been given to this point of view in recent years. For example, an elliptic curve cryptosystem whose key length is 224 bits, can handle calculation processing with a calculated amount of about 1/7 as compared with a RSA system whose key length is 1024 bits. Thus, the elliptic curve cryptosystem was considered to be better-suited for an IC card, particularly a wireless IC card as the field of application using the elliptic curve cryptosystem. In the wireless IC card, the third party is capable of easily intercepting communication data and the wireless IC card cannot get by with avoiding encryption of the data. While the wireless IC card has the merit of being capable of passing through a gate with being non-contact, it must break a cipher and authenticate it during its short passage time. It is thus necessary to provide a reside computing device which efficiently executes a residue arithmetic operation or the like in the elliptic curve cryptosystem.
When it is desired to execute the residue arithmetic operation or the like, dedicated LSI or a processor equipped with a multiplier of about 32 bits performs calculations by, for example, a method of dividing a bit length of a long key every 32 bits and carrying out calculations. An algorithm for avoiding division by preference has been adopted for the calculations. This is a contrivance for reducing a chip size. As the above algorithm, it has been known that a calculation time interval becomes short if the Montgomery method, for example.
However, such a method using a multiplier having a less number of bits has many problems. The method is accompanied by a drawback that since a complex algorithm is used, the amount of calculations increases, and a clock should be unavoidably made fast from the need for the calculations in a short period of time, thereby increasing current consumption. Further, since data being in the course of their calculations must be stored in their corresponding registers or the like and a number of the registers are used, the amount of circuitry cannot be reduced so far.
An increase in current consumption will impose a restriction on a wireless IC card, particularly, a wireless IC card of such a type that power is supplied in the form of external electromagnetic waves. An increase in the size of a chip will raise the cost of wireless IC cards supplied in large quantities.